/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 * 
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "haha",
    /* First member's full name */
    "deconx",
    /* First member's email address */
    "deconx@qq.com",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)


#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4   //单字，块头部和尾部的大小
#define DSIZE 8   //双字
#define VOID_EXTEND (1<<12)    //堆默认扩展大小
#define TYPE_SIZE 20    //分离空闲链表个数

#define PACK(size,allocation) ((size)|(allocation))   //设置块头部和尾部
#define GET(point) (*(unsigned int*)(point))    //读取指针的值
#define PUT(point,val) ((*(unsigned int*)(point))=(val))    //向指针中写入值

#define GET_BLOCK_SIZE(point) (GET(point)&(~0x7))   //获取块大小
#define GET_ALLOCATION(point) (GET(point)&0x1)   //获取块是否已分配

//bp指向有效载荷起始位置
#define HEAD(bp) ((char*)(bp)-WSIZE)    //获取有效载荷头部
#define FOOT(bp) ((char*)(bp)+GET_BLOCK_SIZE(HEAD(bp))-DSIZE)    //获取有效载荷尾部
#define NEXT(bp) ((char*)(bp)+GET_BLOCK_SIZE(((char*)(bp)-WSIZE)))    //获取有效载荷的后继
#define PREV(bp) ((char*)(bp)-GET_BLOCK_SIZE(((char*)(bp)-DSIZE)))    //获取有效载荷前驱

#define MAX(x1,x2) ((x1)>(x2)?(x1):(x2))

static char *heap_list;    //堆的头指针

#define GET_HEAD(n) ((unsigned int* )(long)(GET(heap_list+WSIZE*n)))   //找到指定序号链表的头指针
#define GET_PREV(bp) ((unsigned int* )(long)(GET(bp)))    //找到bp前驱
#define GET_NEXT(bp) ((unsigned int* )(long)(GET((unsigned int*)bp+1)))    //找到bp后继

int mm_check(void);   //堆一致性检查
static void* extend_heap(size_t words);     //扩展堆
static void* coalesce(void* bp);            //合并空闲块
static void* first_fit(size_t size);        //首次适配
static void place(void* bp,size_t size);   //分割空闲块
static void delete(void* bp);               //从相应链表中删除块
static void insert(void* bp);               //在相应链表中插入块
static int search(size_t size);             //根据块大小找到头节点位置


/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    if((heap_list=mem_sbrk((4+TYPE_SIZE)*WSIZE))==(void* )-1)    //堆开头的四个字，消除边界特别的影响
        return -1;
    
    //初始化各类块大小链表
    for(int i=0;i<TYPE_SIZE;i++)
        PUT(heap_list+i*WSIZE, NULL);
    
    //考虑对齐
    PUT(heap_list+TYPE_SIZE*WSIZE,0);
    
    //序言块结尾块设置为已分配
    PUT(heap_list+((1+TYPE_SIZE)*WSIZE),PACK(DSIZE,1));
    PUT(heap_list+((2+TYPE_SIZE)*WSIZE),PACK(DSIZE,1));
    PUT(heap_list+((3+TYPE_SIZE)*WSIZE),PACK(0,1));

    //扩展堆
    if(extend_heap(VOID_EXTEND/WSIZE)==NULL)
        return -1;
    return 0;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void* mm_malloc(size_t size)
{
    size_t sizec;
    size_t size_ex;
    char* bp;
    if(size==0)
        return NULL;

    //考虑对齐
    if(size<=DSIZE)
        sizec=2*DSIZE;
    else
        sizec=DSIZE*((size+(DSIZE)+(DSIZE-1))/DSIZE);

    //首次适配找到合适空闲块
    if((bp=first_fit(sizec))!=NULL)
    {
        place(bp,sizec);
        return bp;
    }
    //当前已经没有合适空闲块则扩展堆
    size_ex=MAX(sizec,VOID_EXTEND);
    if((bp=extend_heap(size_ex/WSIZE))==NULL)
        return NULL;
    //扩展后分割
    place(bp,sizec);
    return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void* ptr)
{
    if(ptr==0)
        return;
    size_t size=GET_BLOCK_SIZE(HEAD(ptr));

    PUT(HEAD(ptr),PACK(size,0));
    PUT(FOOT(ptr),PACK(size,0));
    coalesce(ptr);
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void* ptr, size_t size)
{
    void* newptr;
    size_t copy_size;
    
    if((newptr=mm_malloc(size))==NULL)    //重新分配
        return 0;
    copy_size=GET_BLOCK_SIZE(HEAD(ptr));
    if(size<copy_size)
        copy_size=size;
    memcpy(newptr,ptr,copy_size);
    mm_free(ptr);
    return newptr;

}

//扩展堆
void* extend_heap(size_t words)
{
    char* bp;
    size_t size;
    //考虑对齐
    if(words%2==1) size=(words+1)*WSIZE;   
    else size=words*WSIZE;

    //扩展
    if((long)(bp=mem_sbrk(size))==-1)
        return NULL;
    
    //设置块的头部和尾部
    PUT(HEAD(bp),PACK(size,0));
    PUT(FOOT(bp),PACK(size,0));
    PUT(HEAD(NEXT(bp)),PACK(0,1));

    return coalesce(bp);    //合并前后空闲块
}


//合并空闲块
void* coalesce(void* bp)
{
    //前后块是否空闲
    size_t prev_alloc=GET_ALLOCATION(FOOT(PREV(bp)));
    size_t next_alloc=GET_ALLOCATION(HEAD(NEXT(bp)));
    size_t size=GET_BLOCK_SIZE(HEAD(bp));    //当前块大小     

    //合并

    //前后都不空闲
    if(prev_alloc&&next_alloc)
    {
        insert(bp);
        return bp;
    }
    //前空后不空
    else if(prev_alloc&&(!next_alloc))
    {
        delete(NEXT(bp));   //将后面的块从其链表中删除
        size+=GET_BLOCK_SIZE(HEAD(NEXT(bp)));  //增加当前块大小
        //修改头部和尾部
        PUT(HEAD(bp),PACK(size,0));
        PUT(FOOT(bp),PACK(size,0)); 
    }
    //前不空后空 
    else if((!prev_alloc)&&next_alloc)
    {
        delete(PREV(bp));    //将前面的块从链表中删除
        size+=GET_BLOCK_SIZE(HEAD(PREV(bp)));  //增加当前块大小
        PUT(FOOT(bp),PACK(size,0));
        PUT(HEAD(PREV(bp)),PACK(size,0));
        bp=PREV(bp);
    }
    //前后都为空
    else
    {
        //将前后两个块都从其链表中删除
        delete(NEXT(bp));
        delete(PREV(bp));
        size+=GET_BLOCK_SIZE(HEAD(PREV(bp)))+GET_BLOCK_SIZE(FOOT(NEXT(bp)));  //增加当前块大小
        PUT(FOOT(NEXT(bp)),PACK(size,0));
        PUT(HEAD(PREV(bp)),PACK(size,0));
        bp=PREV(bp);
    }
    insert(bp);    //将空闲块插入相应链表
    return bp;
}

//首次适配
void* first_fit(size_t size)
{
    int n=search(size);
    unsigned int* bp;
    
    while(n<TYPE_SIZE)   //寻找合适大小的链表
    {
        bp=GET_HEAD(n);
        while(bp) 
        {
            if(GET_BLOCK_SIZE(HEAD(bp))>=size)
                return (void* )bp;
            bp=GET_NEXT(bp);
        }
        ++n;
    }
    return NULL;
}

//分割空闲块
void place(void* bp, size_t size)
{
    size_t sizec=GET_BLOCK_SIZE(HEAD(bp));
    
    //判断是否需要分割
    delete(bp);

    if((sizec-size)>=2*DSIZE)
    {
        PUT(HEAD(bp),PACK(size,1));
        PUT(FOOT(bp),PACK(size,1));
        bp=NEXT(bp);
        PUT(HEAD(bp),PACK(sizec-size,0));
        PUT(FOOT(bp),PACK(sizec-size,0));

        insert(bp);
    }
    else    //大小正好直接放置
    {
        PUT(HEAD(bp),PACK(sizec,1));
        PUT(FOOT(bp),PACK(sizec,1));
    }
}

//插入块至相应链表
void insert(void* bp)
{
    size_t size = GET_BLOCK_SIZE(HEAD(bp));    //块大小
    int n=search(size);   //寻找相应块的链表

    //如果没有合适的链表则新创建
    if(GET_HEAD(n)==NULL)
    {
        //设置新链表
        PUT(heap_list+WSIZE*n,bp);
        PUT(bp,NULL);
        PUT((unsigned int*)bp+1,NULL);
	} 
    else
    {
        //插入块
		PUT((unsigned int*)bp+1,GET_HEAD(n));
        PUT(GET_HEAD(n),bp);	
		PUT(bp,NULL);
		PUT(heap_list+WSIZE*n,bp);
	}
}

//删除块
void delete(void* bp)
{
    size_t size=GET_BLOCK_SIZE(HEAD(bp));
    int n=search(size);
    
    //如果只有一个节点
	if(GET_PREV(bp)==NULL&&GET_NEXT(bp)==NULL) 
		PUT(heap_list+WSIZE*n,NULL);
    //若为最后一和节点
    else if(GET_PREV(bp)!=NULL&GET_NEXT(bp)==NULL) 
		PUT(GET_PREV(bp)+1, NULL);
    //若为第一个节点
    else if(GET_NEXT(bp)!=NULL&&GET_PREV(bp)==NULL)
    {
		PUT(heap_list+WSIZE*n,GET_NEXT(bp));
        PUT(GET_NEXT(bp), NULL);
	}

    else if(GET_NEXT(bp)!=NULL&&GET_PREV(bp)!=NULL) 
    {
		PUT(GET_PREV(bp)+1,GET_NEXT(bp));
		PUT(GET_NEXT(bp),GET_PREV(bp));
	}
}

//寻找相应大小的块
int search(size_t size)
{
    int i;
    for(i=4;i<=22;i++)
    {
        if(size<=(1<<i))
            return i-4;
    }
    return i-4;
}

int mm_check(void)
{
    int is=1;

    
    for(int i=0;i<TYPE_SIZE;i++)
    {
        unsigned int* po=GET_HEAD(i);
        while(GET_BLOCK_SIZE(HEAD(po)))
        {
            //空闲列表中的指针是否指向有效的空闲块
            if(po==NULL) 
            {
                printf("There exists some point in the free list null\n");
                is=0;
            }
            //每个空闲链表中的块是否都标记为free
            if(GET_ALLOCATION(HEAD(po)))
            {
                printf("There exists some free blocks not noted.\n");
                is=0;
            }

            po=NEXT(po);
        }
    }

    char* po=heap_list+((2+TYPE_SIZE)*WSIZE);
    while(GET_BLOCK_SIZE(HEAD(po)))
    {
        // 堆块中的指针是否指向有效的堆地址？
        if(po==NULL)
        {
            printf("There exsits some point in heap null.\n");
            is=0;
        }

        //是否存在未合并的空闲块
        if(GET_ALLOCATION(HEAD(po))==0&&GET_ALLOCATION(HEAD(NEXT(po)))==0)
        {
            printf("There exists some free blocks not merged.\n");
            is=0;
        }

        //已分配的块是否存在重叠现象？
        if(GET_ALLOCATION(HEAD(po))&&GET_ALLOCATION(HEAD(NEXT(po))))
        {
            if(po+GET_BLOCK_SIZE(HEAD(po))!=NEXT(po))
            {
                printf("There exsits some allocated blocks overlaped.\n");
                is=0;
            }
        }
        po=NEXT(po);
    }


    return is;
}